#include <stdio.h>
#define MAXSIZE 20

struct Node{
	int data;
	Node* next;
};
struct hashN{
	Node* data;
	hashN* next;
};
hashN* mhash[MAXSIZE];

void insertHash(Node* node)
{
        int ind=(size_t)node/4%MAXSIZE;
        hashN* tmp=new hashN;
        tmp->data=node;
        tmp->next=0;
        if(mhash[ind]==0)
        {
                mhash[ind]=tmp;
        }
        else
        {
                tmp->next=mhash[ind];
                mhash[ind]=tmp;
        }
}
int findHash(Node* node)
{
        int ind=(size_t)node/4%MAXSIZE;
        hashN* tmpN=mhash[ind];
        while(tmpN!=0)
        {
                if(node==tmpN->data)
                        return ind;
                tmpN=tmpN->next;
        }
        return -1;
}

Node* findCross(Node* list1,Node* list2)
{
       while(list1!=0)
       {
                if(findHash(list1)!=-1)
                        break;
                else
                {
                	insertHash(list1);
                	list1=list1->next;
                }
       } 
       while(list2!=0)
       {
       		int res=findHash(list2);
       		if(res!=-1)
       			return list2;
       		list2=list2->next;
       }
}
void printList(Node* list)
{
	while(list!=0)
	{
		printf("%d ",list->data);
		list=list->next;
	}
	printf("\n");
}
void printHash()
{
	for(int i=0;i<MAXSIZE;i++)
	{
		printf("%d:",i);
		hashN* tmpN=mhash[i];
		while(tmpN!=0)
		{
			printf("%d ",tmpN->data->data);
			tmpN=tmpN->next;
		}
		printf("\n");
	}
}
void reverList(Node* &list)
{
	Node* i,*j;
	i=list;j=0;
	while(i!=0)
	{
		Node* tmp=i;
		i=i->next;
		tmp->next=j;
		j=tmp;
	}
	list=j;
}
bool isCycle(Node* list)
{
	Node* head=list;
	reverList(list);
	return head==list;
}
int main()
{
	for(int i=0;i<MAXSIZE;i++)
	{
		mhash[i]=0;
	}
	Node* list1=0;
	Node* list2=0;
	for(int i=0;i<10;i++)
	{
		Node* tmp=new Node;
		tmp->data=i;
		tmp->next=0;
		if(list1==0)
		{
			list1=tmp;
		}
		else
		{
			tmp->next=list1;
			list1=tmp;
		}

	}
	Node* tmp=new Node;
	tmp->data=-1;
	tmp->next=list1->next->next;
	list2=tmp;
	
	printList(list1);
	printList(list2);
	printHash();
	
	printf("%d\n",findCross(list1,list2)->data);
	printHash();
	
	//reverList(list1);
	//printList(list1);
	Node* list3=new Node;
	list3->next=list3;
	if(isCycle(list3))
		printf("yes\n");
	else
		printf("no\n");
	return 0;
}
